package com.zhugang.week13.array;

import java.util.Arrays;

/**
 * @program algorithms
 * @description: merge
 * @author: chanzhugang
 * @create: 2022/09/16 09:00
 */
public class Merge {

    /**
     * 88 合并两个有序数组
     * https://leetcode.cn/problems/merge-sorted-array/
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // nums2 to nums1
        // 逆向双指针, 三指针更好，推荐这种
        int i = m - 1;
        int j = n - 1;
        int cur = nums1.length - 1;

        // nums2合并完就结束
        while (j >= 0) {
            if (i >= 0 && nums1[i] >= nums2[j]) {
                nums1[cur--] = nums1[i--];
            } else {
                nums1[cur--] = nums2[j--];
            }
        }
    }


    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        // nums2 to nums1
        // 逆向双指针，分情况套路，类似归并排序
        int i = m - 1;
        int j = n - 1;
        int tail = m + n - 1;
        int curVal = 0;
        while (i >= 0 || j >= 0) {
            if (i == -1) {
                curVal = nums2[j--];
            } else if (j == -1) {
                curVal = nums1[i--];
            } else if (nums1[i] >= nums2[j]) {
                curVal = nums1[i--];
            } else if (nums2[j] > nums1[i]) {
                curVal = nums2[j--];
            }
            nums1[tail--] = curVal;
        }
    }


    public void merge3(int[] nums1, int m, int[] nums2, int n) {
        // 直接把nums2合并到nuns1尾部，再排序，不推荐
        for (int i = 0; i < n; i++) {
            nums1[m++] = nums2[i];
        }
        Arrays.sort(nums1);
    }


}